public class FIFOReplacement {
    //先进先出算法
    public static int lackTimes;

    public double replace(int[] pagesSequence, int memoryBlocks){
        //记录缺页次数
        lackTimes = 0;
        //当前页框数
        int[] memory = new int[memoryBlocks];
        //当前的位置
        int curIndex = 0;
        //将所有的内存块置为-1为空闲状态
        for (int i = 0;i<memoryBlocks;i++){
            memory[i]=-1;
        }
        //在内存中寻找页，找到则不操作，没找到则替换最早放入的内存块
        for (int i = 0;i<pagesSequence.length;i++){
            if(searchIndex(pagesSequence[i], memory) == -1){
                //当内存满时才开始计算缺页率
                if(memory[memory.length-1] != -1){
                    lackTimes++;
                }
                //替换内存块
                memory[curIndex] = pagesSequence[i];
                curIndex = (curIndex+1)%memoryBlocks;
            }
        }
        //返回缺页率
        return (lackTimes * 1.0/pagesSequence.length);
    }
    
    //寻找是否在内存中
    public int searchIndex(int page, int[] memory) {
        for(int i=0;i<memory.length;i++){
            if(page==memory[i]){
                return i;
            }
        }
        return -1;
    }
}
